package C048;

import java.util.Arrays;

/**
 * ClassName: C05
 * Package: C048
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/2/15 17:37
 * @Version 1.0
 * @Since 1.0
 */
public class C05 {
    public static void main(String[] args) {
//        long[] arr = {1,5,2,2,2,3,3,4};
//        System.out.println(sort(arr));
//        System.out.println(Arrays.toString(arr));
         int[][] arr = {{0,0,1},{1,0,1}};
//         int[][] arr = {{4,4,6},{7,5,3},{1,6,2},{5,6,3}};
        System.out.println(fieldOfGreatestBlessing(arr));

    }


    public static int fieldOfGreatestBlessing(int[][] forceField) {
        long[] xs = new long[forceField.length * 2];
        long[] ys = new long[forceField.length * 2];
        long x, y, r;
        for (int i = 0, p1 = 0, p2 = 0; i < forceField.length; i++) {
            x = forceField[i][0];
            y = forceField[i][1];
            r = forceField[i][2];
            xs[p1++] = (x << 1) - r;
            xs[p1++] = (x << 1) + r;
            ys[p2++] = (y << 1) - r;
            ys[p2++] = (y << 1) + r;
        }

        // 计算有效的范围
        int xsize = sort(xs);
        int ysize = sort(ys);
        int[][] arr = new int[xs.length + 2][ys.length + 2];
        int r1, c1, r2, c2;
        for (int i = 0; i < forceField.length; i++) {
            x = forceField[i][0];
            y = forceField[i][1];
            r = forceField[i][2];
            r1 = rank(xs, (x << 1) - r, xsize);
            c1 = rank(ys, (y << 1) - r, ysize);
            r2 = rank(xs, (x << 1) + r, xsize);
            c2 = rank(ys, (y << 1) + r, ysize);
            set(arr, r1, c1, r2, c2);
        }

        int ans = Integer.MIN_VALUE;
        for (int i = 1; i <= xsize; i++) {
            for (int j = 1; j <= ysize; j++) {
                arr[i][j] += arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1];
                ans = Math.max(ans, arr[i][j]);
            }
        }

        return ans;
    }

    private static void set(int[][] arr, int r1, int c1, int r2, int c2) {
        r2++;
        c2++;
        arr[r1][c1] += 1;
        arr[r2][c1] -= 1;
        arr[r1][c2] -= 1;
        arr[r2][c2] += 1;
    }


    private static int rank(long[] arr, long num, int size) {
        int l = 0, r = size - 1;
        int m = 0;
        while (l <= r) {
            m = l + ((r - l) >> 1);
            if (arr[m] > num) {
                r = m - 1;
            } else if (arr[m] < num) {
                l = m + 1;
            } else {
                // 相等
                return m + 1;
            }
        }
        return -1;
    }

    private static int sort(long[] arr) {
        Arrays.sort(arr);
        int size = 0;
        for (int i = 1; i < arr.length; i++) {
            if(arr[i] != arr[i - 1]) {
                arr[++size] = arr[i];
            }
        }
        return size + 1;
    }
}
